1. Field of the Invention
The present invention generally relates to Time Division Duplex (TDD) indoor wireless communication networks and, more particularly, to a scheduling algorithm for providing Quality of Service (QoS) by controlling medium access in communication networks. In particular, it can be applied to Master-driven TDD wireless systems for maximizing the schedulable utilization (i.e., maximizing utilization under QoS constraints) of the system and for meeting QoS requirements like token rate and latency (maximum delay).
2. Background Description
Bluetooth(trademark) is a computing and telecommunications industry specifications that describes how mobile phones, computers, personal digital assistants (PDAs), and other devices can interconnect using a short range wireless connection. Each device is equipped with a microchip transceiver that transmits and receives in the frequency band of 2.45 GHz. Each device will have a unique 48-bit address from the Institute of Electrical and Electronics Engineers (IEEE) 802 standard. Connections are one-to-one, and the maximum range is ten meters. Data can be exchanged at a rate of one megabits per second (Mbs) and up to two Mbs in the second generation of the technology. The five founding companies of the Bluetooth(trademark) Special Interest Group (SIG) are Ericsson, International Business Machines (IBM), Intel, Nokia; and Toshiba. Additional information may be had by reference to the Web site www.bluetooth.com and an article by Andrew Seybold entitled xe2x80x9cBluetooth Technology: The Convergence of Communications and Computingxe2x80x9d, reprinted from Andrew Seybold""s Outlook, May 1998, on the World Wide Web at www.gsmdata.com/artblue.htm.
Indoor wireless networks based on standards such as Bluetooth(trademark) use frequency hopping to combat the problem of interference from sources such as microwave ovens and cordless telephones, which also use frequencies in the same band. In practical environments, in addition to active interfering sources, there can also be objects such as water fountains and racks of bottles with water content which absorb much of the radiation in the 2.45 GHz band and obstruct communication between master and slave units in the vicinity. Therefore, a master unit needs to detect such problems in communication and take necessary actions to prevent loss of packets during the periods of interference.
In the current Bluetooth(trademark) standard, due to frequency hopping, the carrier frequency used in consecutive time slots is a different one of several different frequencies within the 2.45 GHz band of frequencies. Therefore, an interference in sub-bands centered around one of these frequencies will only affect communication during that time-slot in which the frequency sub-band is used. Further, in the Bluetooth(trademark) standard, a packet can occupy one, three or five time slots, and in the case of multiple size packets, the same frequency as fixed for the first time slot is used. Because of this, it is possible to mask the effect of an interference by transmitting a packet of appropriate size. For example, if it is known that there is high chance of interference in one of the second through fifth time slots, and very low probability of the first time slot being bad, it is possible to skip the frequencies corresponding to second through fifth time slots by transmitting a five time-slot packet instead of one or three time-slot packets.
The characterization of link between any Slave unit and the Master can be done by the Master unit based on the receipt or otherwise of acknowledgments received from the Slave unit. Alternatively, all the Slaves can record the number of times they detect good packet headers sent by the Master to any Slave. This information can be transmitted from the Slaves to the Master at periodic intervals of time. The Master can use this information along with frequency look-ahead to determine the next Slave for communication and also the appropriate packet size.
Master-driven TDD can be described briefly as follows in the context of a pico-cellular system, such as the Bluetooth(trademark) standard. Each cell or pico-net comprises of a Master device and several Slave devices. Each device can either send or receive in a slot. The Master controls the traffic on the pico-net and schedules the Slaves on the wireless channel. The Master schedules a Slave by sending a packet addressed to it, and the Slave replies with its own transmission in the next slot. Thus, Master and Slave transmissions are coupled and controlled by the Master.
Providing Quality of Service (QoS) to the connections makes the scheduling policy very important. QoS is defined by various parameters for different systems. These parameters are negotiated between the Master and the Slave at the time of connection establishment. The link layer QoS parameters for data sessions that we consider are described below:
Token Rate: This is the rate at which data should be drained from the buffer corresponding to a data connection.
Token Bucket size: This is the maximum buffer size that the connection might require. It is assumed that when the buffer is full, any new incoming data is discarded.
Peak Bandwidth: This is the maximum rate at which a burst of data enters the buffer.
Latency: This is the maximum delay that can be tolerated by a single packet.
Maximum burst size: This is the maximum size of a single burst.
Average arrival rate: This is the maximum rate at which data can arrive after a burst has arrived, while the buffer is not empty.
All the above parameters are mapped to a Polling Interval (PI), which is the only parameter that is known to the scheduler, implemented at the Master. The polling interval is defined as the maximum time between two consecutive polls to the same connection. The right choice of this parameter would ensure that data is emptied from the buffer at the required token rate, and the scheduling method which uses this polling interval would ensure that the latency requirement of each connection is met. The polling interval is also dependent on the maximum packet size for a session, and has to be re-calculated every time the maximum packet size changes.
It is assumed that there are two types of sessionsxe2x80x94guaranteed and best-effort. For guaranteed sessions, a violation of the QoS parameters results in an exception and the parameters are renegotiated. For best-effort sessions, a temporary violation of the QoS parameters is not that serious. However, even for best-effort sessions, whenever there is a buffer overflow, a violation is raised and the parameters are renegotiated.
There has been a considerable amount of research on scheduling algorithms for communication networks. However, none of these consider the problem of scheduling connections with QoS constraints on a polling based Media Access Control (MAC) layer which does not allow reservations. Some of them are listed below:
S. Lu, V. Bliargavan and R. Srikant, in xe2x80x9cFair Scheduling in Wireless Packet Networksxe2x80x9d, ACM SIGCOMM""97, August 1997, describe a model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error blasts. They describe an algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions.
D. Ferrari and D. Verma, in xe2x80x9cA Scheme for Real-Time Channel Establishment in Wide-Area Networksxe2x80x9d, IEEE Journal on Selected Areas in Communications, pp. 368-379, April 1990, explore the feasibility of providing real-time services on a packet-switched store-and-forward wide-area network with general topology. The describe a scheme for the establishment of channels with deterministic or statistical delay bounds.
R. L. Cruz, in xe2x80x9cQuality of Service Guarantees in Virtual Circuit Switched Networksxe2x80x9d, IEEE Journal on Selected Areas in Communications, vol. 13, no. 6, August 1995, reviews some recent results regarding the problem of providing deterministic quality of service guarantees in slot-based virtual circuit switched networks.
Manish Kalia, Deepak Bansal and Rajeev Shorey, in xe2x80x9cMAC Scheduling and SAR policies for Bluetooth: A Master Driven TDD Pico-cellular Wireless Systemxe2x80x9d, Mobile, Multimedia Conference 1999, pp. 384-388, describe data scheduling and Segmentation and Reassembly (SAR) polling in Master driven TDD pico-cellular wireless system conforming to the Bluetooth(trademark) standard.
K. Jeffay, D. F. Stanat and C. U. Martel, in xe2x80x9cOn Non-Preemptive scheduling of Periodic and Sporadic Tasksxe2x80x9d, Proceedings Real Time System Symposium, 1991, exam the problem of scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. They show that any set of periodic or sporadic tasks that satisfy certain conditions can be scheduled with an earliest deadline first (EDF) scheduling algorithm.
U.S. patent application Ser. No. 09/434,583 filed Nov. 4, 1999, by Rajeev Shorey, Deepak Bansal and Manish Kalia, for xe2x80x9cMedia Access Control Scheduling Methodology in Master Driven Time Division Duplex Wireless Pico-Cellular Systemsxe2x80x9d, describes a scheduling strategy that does not take the QoS requirements of different connections into considerations.
U.S. Pat. No. 5,506,848 to Drakopoulos et al. for xe2x80x9cDemand Assignment System and Method for Mobile Users in a Community of Interestxe2x80x9d, describes a slot reservation system in which is not possible for data in packet switched networks.
U.S. Pat. No. 5,274,841 to Natarajan et al. for xe2x80x9cMethods for Polling Mobile Users in a Multiple Cell Wireless Networkxe2x80x9d, describes methods for polling mobile users. Here uplink access is done using Carrier Sense Multiple Access which is different from a polling interval based polling model.
U.S. Pat. No. 5,297,144 to Gilbert et al. for xe2x80x9cReservation-based Polling Protocol for a Wireless Data Communication Networkxe2x80x9d, describes a reservation based polling system which is again different from a polling interval based polling.
According to the present invention, there is provided a scheduling algorithm which maximizes the schedulable utilization and also meets the QoS requirements of each connection. The method is simple to implement and ensures fairness to all connections. The method also includes scheduling of periodic voice slots along with data connections and also incorporates rules for handling wireless errors. The algorithm can be labeled as xe2x80x9cAdaptive Per-connection Deadline Scheduling Algorithmxe2x80x9d, which makes use of the polling interval, which was described in the previous section.
Several scheduling algorithms have been proposed in the literature which maximize the schedulable region among a set of connections. These fall under the Earliest-Deadline-First,(EDF) class of algorithms. However, these policies set per-packet deadlines. The deadline of a packet for a connection is its arrival time plus the maximum tolerable delay of that connection. The packets are then served earliest deadline first. However, these are difficult to implement as packet arrival times need to be taken into account.
Our method uses per-queue deadlines instead of per-packet deadlines. Each connection has a queue where packets to be transmitted are enqueued. The deadline for a queue is set at the time the scheduler departs from the queue. The deadline is the sum of the departure time and the polling interval for that connection. The polling interval is derived based on the QoS requirements in terms of the parameters mentioned in the previous section. The queue with the earliest deadline is served first. The service discipline we use is k-limited. This means that the number of packets served in each visit is k. The value of k could be different for different queues.
We model each guaranteed connection as a periodic task with deadlines. The period of a task depends upon the polling interval of the corresponding session.
For best-effort (non-guaranteed) sessions, the polling interval is increased or decreased based on whether the number of packets actually in the queue is greater or lesser than the quantum k. If the number of packets actually served is less, which means the session is using less bandwidth than it asked for, then the next deadline is extended to allow other connections to make use of the excess bandwidth. Similarly, if the number of packets in the queue is more than k, then the session requires more bandwidth at this instant than it asked for. Hence we advance the next deadline to reduce the chances of a buffer overflow. If the number of packets left in a queue after the scheduler serves k packets is zero, then the polling interval is not changed.
To ensure that no guaranteed session misses its deadline because of a best-effort session requiring extra bandwidth, a best-effort session is scheduled only in the idle times of the processing flow of guaranteed sessions. This ensures that guaranteed services are not affected by best-effort services and the admission control for guaranteed services can be applied without accounting for best-effort services.
The algorithm also has provisions for scheduling voice slots along with data sessions. Besides these, we give rules to be followed for scheduling in the presence of wireless errors.